package com.test.daily.leetcode.y2022.m07.day0712.v02;

import java.util.Stack;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/12 下午 06:47
 * @version: 1.0
 */
public class Solution {
   public static void swap(int[] arr, int i, int j){
       int tmp = arr[i];
       arr[i] = arr[j];
       arr[j] = tmp;
   }
   public static int partition(int[] arr, int L, int R){
       if(L > R){
           return -1;
       }
       if(L == R){
           return L;
       }
       int less = L -1;
       int index = L;
       while(index < R){
           if(arr[index] < arr[R]){
               swap(arr, index, ++less);
           }
           index++;
       }
       return less;
   }
   public static int[] netherlandFlag(int[] arr, int L, int R){
       if(L > R){
           return new int[]{-1, -1};
       }
       if(L == R){
           return new int[]{L, L};
       }
       int less = L - 1;
       int index = L;
       int more = R;
       while(index < more){
           if(arr[index] == arr[R]){
               index++;
           } else if(arr[index] < arr[R]){
               swap(arr, index++, ++less);
           }else{
               swap(arr, index, --more);
           }
       }
       swap(arr, R, more);
       return new int[]{less + 1, more};
   }
   public static class Op{
       int L;
       int R;
       public Op(int left, int right){
           this.L = left;
           this.R = right;
       }
   }
   public static void quickSort3(int[] arr){
        swap(arr, arr.length - 1, (int)Math.random()*(arr.length));
        int[] equals = netherlandFlag(arr, 0, arr.length - 1);
        Stack<Op> stack = new Stack();
        stack.push(new Op(0, equals[0]));
        stack.push(new Op( equals[1], arr.length - 1));
        while(!stack.isEmpty()){
            Op op = stack.pop();
            int left = op.L;
            int right = op.R;
            if(left < right){
                swap(arr, right, left + (int)Math.random()*(right - left + 1));
                equals = netherlandFlag(arr, left, right);
                stack.push(new Op(op.L,equals[0]));
                stack.push(new Op(equals[1],op.R));

            }
        }
   }
}
